package LearnAlgorithm.f_字符串;

import java.util.Arrays;


/*
给定一段产品的英文描述，包含M个英文单词，每个英文单词以空格分隔，无其他标点符号
再给定N个英文单词关键字
目标是找出此产品描述中包含N个关键字(每个关键词至少出现1次)的长度最短的子串
 */
public class k返回最短摘要 {
	public static void main(String[] args) {
		String[] sentenceW = new String[] {"a","b","c","d","h","e","f","g","c","d","e","f","d","c"};
		String[] keys = new String[] {"c","e"};
		String[] sentenceW1 = new String[] {"a","b","x","d","x","a","y","g","z","d","e","f","y","c"};
		String[] sentenceW2 = new String[] {"a","b","x","d","y","a","x","g","z","d","e","f","y","c"};
		String[] keys1 = new String[] {"x","y","z"};
		long before = System.currentTimeMillis();
//		findForce(sentenceW, keys);
//		findDoublePointer(sentenceW, keys);
		findDoublePointerPlus(sentenceW2, keys1);
		util.Util.duration(before);
	}
	
	/**
	 * O(M*N)
	 * @param sentence
	 * @param keys
	 */
	public static void findDoublePointerPlus(String[] sentence, String[] keys) {
		int childArrBeginIndex = -1;//定义目标子数组的开始索引
		int childArrEndIndex = -1;//定义目标子数组的结束索引
		int previousLastKeyIndex = -1;//定义上一个目标子数组的结束索引；
		int childArrMinLength = Integer.MAX_VALUE;//定义目标子数组的长度
		int[] keysElementsStatus = new int[keys.length];//定义存储“关键字数组的元素状态”的status数组；1表示找到
		for (int firstKeyIndex = 0; firstKeyIndex < sentence.length; firstKeyIndex++) {//最外层循环；跳出就结束
//			Arrays.fill(keysElementsStatus, 0);//重置status数组
			String FirstCurrentSentenceWord = sentence[firstKeyIndex];//假设第一个出现的关键字a
			int firstCurrentSentenceWordIndexFromKeys = indexOf(keys, FirstCurrentSentenceWord);//判断a是否在keys中；判断我们的假设是否正确
			if (firstCurrentSentenceWordIndexFromKeys == -1) {//假设错误
				continue;//跳出本次；去假设下一个sentence元素是否为关键字
			} else {
				if (keysElementsStatus[firstCurrentSentenceWordIndexFromKeys] == 0) {//假设通过；判断是否0
					keysElementsStatus[firstCurrentSentenceWordIndexFromKeys]++;//是0就代表“上个循环q0之后跟的是q1”,那么++
				}//不是0就代表“上个循环q0之后跟的还是q0”,不进行任何操作
//				keysElementsStatus[firstCurrentSentenceWordIndexFromKeys] = 1;//假设通过；keys中对应的关键字被标记为“找到”；status中对应的索引的值打上1
			}
			int lastKeyIndex = 0;//定义最后一个关键字的索引
			if (previousLastKeyIndex != -1) {
				lastKeyIndex = previousLastKeyIndex;//存在上一个“最后一个关键字的索引”；拿过来使用
			} else {
				lastKeyIndex = firstKeyIndex + 1;//上一个“最后一个关键字的索引”是-1；代表外循环第一次找到“第一个关键字”；就把sentence中的“第一个关键字”的索引firstKeyIndex的值+1赋值给“最后一个关键字的索引”lastKeyIndex
			}
			while (lastKeyIndex < sentence.length) {//此循环寻找剩下的所有关键字
				String CurrentSentenceWord = sentence[lastKeyIndex];//再一次假设关键字
				int currentSentenceWordIndexFromKeys = indexOf(keys, CurrentSentenceWord);
//				if (currentSentenceWordIndexFromKeys == -1 || keysElementsStatus[currentSentenceWordIndexFromKeys] == 1) {
				if (currentSentenceWordIndexFromKeys == -1) {//判断假设
					lastKeyIndex++;
					continue;
				} else {
					keysElementsStatus[currentSentenceWordIndexFromKeys]++;//lastKeyIndex被判断通过；只管++就完事了
					if (checkAll(keysElementsStatus)) {//判断目标子数组是否完整包含所有关键字
						previousLastKeyIndex = lastKeyIndex;//保存lastKeyIndex
						if (lastKeyIndex - firstKeyIndex + 1 < childArrMinLength) {//判断是否符合最小摘要
							childArrMinLength = lastKeyIndex - firstKeyIndex + 1;
							childArrBeginIndex = firstKeyIndex;
							childArrEndIndex = lastKeyIndex;
						}
						resetStatus(keysElementsStatus, firstCurrentSentenceWordIndexFromKeys, currentSentenceWordIndexFromKeys);//不管是否符合最小摘要，都要进行重置状态数组的操作；或者说，只要通过了checkAll(keysElementsStatus)，就需要重置
						break;
					}
				}
				lastKeyIndex++;
			}
		}
		printResult(sentence, childArrBeginIndex, childArrEndIndex, childArrMinLength);
	}
	
	/**
	 * O(M*N)
	 * 老师的想法有缺陷
	 * 是不正确的程序
	 * @param sentence
	 * @param keys
	 */
	public static void findDoublePointer(String[] sentence, String[] keys) {
		int childArrBeginIndex = -1;//定义目标子数组的开始索引
		int childArrEndIndex = -1;//定义目标子数组的结束索引
		int previousLastKeyIndex = -1;//定义上一个目标子数组的结束索引；
		int childArrMinLength = Integer.MAX_VALUE;//定义目标子数组的长度
		int[] keysElementsStatus = new int[keys.length];//定义存储“关键字数组的元素状态”的status数组；1表示找到
		for (int firstKeyIndex = 0; firstKeyIndex < sentence.length; firstKeyIndex++) {//最外层循环；跳出就结束
			Arrays.fill(keysElementsStatus, 0);//重置status数组
			String FirstCurrentSentenceWord = sentence[firstKeyIndex];//假设第一个出现的关键字a
			int firstCurrentSentenceWordIndexFromKeys = indexOf(keys, FirstCurrentSentenceWord);//判断a是否在keys中；判断我们的假设是否正确
			if (firstCurrentSentenceWordIndexFromKeys == -1) {//假设错误
				continue;//跳出本次；去假设下一个sentence元素是否为关键字
			} else {
				keysElementsStatus[firstCurrentSentenceWordIndexFromKeys] = 1;//假设通过；keys中对应的关键字被标记为“找到”；status中对应的索引的值打上1
			}
			int lastKeyIndex = 0;//定义最后一个关键字的索引
			if (previousLastKeyIndex != -1) {
				lastKeyIndex = previousLastKeyIndex;//存在上一个“最后一个关键字的索引”；拿过来使用
			} else {
				lastKeyIndex = firstKeyIndex + 1;//上一个“最后一个关键字的索引”是-1；代表外循环第一次找到“第一个关键字”；就把sentence中的“第一个关键字”的索引firstKeyIndex的值+1赋值给“最后一个关键字的索引”lastKeyIndex
			}
			while (lastKeyIndex < sentence.length) {//此循环寻找剩下的所有关键字
				String CurrentSentenceWord = sentence[lastKeyIndex];//再一次假设关键字
				int currentSentenceWordIndexFromKeys = indexOf(keys, CurrentSentenceWord);
				if (currentSentenceWordIndexFromKeys == -1 || keysElementsStatus[currentSentenceWordIndexFromKeys] == 1) {
					lastKeyIndex++;
					continue;
				} else {
					keysElementsStatus[currentSentenceWordIndexFromKeys] = 1;
					if (sumAll(keysElementsStatus) == keysElementsStatus.length) {
						previousLastKeyIndex = lastKeyIndex;
						if (lastKeyIndex - firstKeyIndex + 1 < childArrMinLength) {
							childArrMinLength = lastKeyIndex - firstKeyIndex + 1;
							childArrBeginIndex = firstKeyIndex;
							childArrEndIndex = lastKeyIndex;
						}
						break;
					}
				}
				lastKeyIndex++;
			}
		}
		printResult(sentence, childArrBeginIndex, childArrEndIndex, childArrMinLength);
	}
	
	/**
	 * 自己思想的判断状态数组方法
	 * 检查数组有没有0
	 * @param arr
	 * @return
	 */
	public static boolean checkAll(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 0) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * 自己思想的“状态数组”的重置方法
	 * @param arr
	 * @param first
	 * @param end
	 */
	public static void resetStatus(int[] arr, int first, int end) {
		arr[first]--;
		arr[end]--;
	}
	
	/**
	 * 老师思想的判断状态数组方法
	 * @param arr
	 * @return
	 */
	public static int sumAll(int[] arr) {
		int result = 0;
		for (int i = 0; i < arr.length; i++) {
			result += arr[i];
		}
		return result;
	}
	
	/**
	 * 寻找key在sentence[]中的索引
	 * 不存在返-1
	 * @param sentence
	 * @param key
	 * @return
	 */
	public static int indexOf(String[] sentence, String key) {
		for (int i = 0; i < sentence.length; i++) {
			if (sentence[i].equals(key)) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 打印输出
	 * @param sentence
	 * @param begin
	 * @param end
	 * @param length
	 */
	public static void printResult(String[] sentence, int begin, int end, int length) {
		System.out.println("begin:" + begin + ", end:" + end);
		for (int i = begin; i <= end; i++) {
			System.out.print(sentence[i] + " ");
		}
		System.out.println();
		System.out.println("length:" + length);
	}
	
	/**
	 * 暴力
	 * O(M^2*N)
	 * @param sentence
	 * @param keys
	 */
	public static void findForce(String[] sentence, String[] keys) {
		int length = Integer.MAX_VALUE;
		int begin = -1;
		int end = -1;
		for (int i = 0; i < sentence.length; i++) {
			for (int j = i + 1; j < sentence.length; j++) {
				if (containsAll(sentence, keys, i, j)) {
					if (j - i < length) {
						begin = i;
						end = j;
						length = end - begin + 1;
					}
				}
			}
		}
		System.out.println("length:" + length);
		System.out.println("begin:" + begin + ", end:" + end);
	}
	
	
	public static boolean containsAll(String[] sentence, String[] keys, int sentenceBegin, int sentenceEnd) {
		int[] helper = new int[keys.length];
		for (int i = sentenceBegin; i <= sentenceEnd; i++) {
			for (int j = 0; j < keys.length; j++) {
				if (sentence[i].equals(keys[j])) {
					helper[j]++;
				}
			}
		}
		for (int i = 0; i < helper.length; i++) {
			if (helper[i] == 0) {
				return false;
			}
		}
		return true;
	}
}
